package step_one;

public class theJumpForg {
    public static void main(String[] args) {
//        青蛙跳台阶
        /*
        1.需求分析：
        一共有n个台阶，青蛙一次只能跳一个台阶或两个台阶，那么一共有m种跳法，求m。
        2.概要设计
        n=1,m=1;        一次跳一阶，有一种跳法
        n=2，m=1+1=2;   一次跳一阶，剩余一阶，有一种跳法；一次跳2阶，上岸，有一种跳法；
        n=3,m=2+1=3;    一次跳一阶，剩余2阶，有两种跳法；一次跳2阶，剩余一阶，有一种跳法；
        n=4,m=3+2=5;    一次跳一阶，剩余3阶，有3种跳法；一次跳2阶，剩余2阶，有两种跳法；
        ...
        可以看到，每次多一阶，跳法都是前两次跳法的和
        3.设计答疑：
        那么我们为什么不算上一次跳n阶台阶呢，比如，n=3，为什么不这样写？
        n=3,m=2+1+1=4;    一次跳一阶，剩余2阶，有两种跳法；一次跳2阶，剩余一阶，有一种跳法；一次跳3阶，只有一种跳法
        原因很简单，因为我们这里用的方法是用已知求未知：即，已经知道n=1，和n=2的时候，m的值，我们不妨充分利用这个数值。
        4.时间复杂度问题
        当n足够大的时候，这些数据的计算量还是有一丢丢耗时的，
        如果不把每次计算出来的结果存储一下，计算下一个m的时候，还需要重复上一次m的计算。很耗时。
        所以要把数据存储下来以节约时间，降低时间开销。
        ps：这里的时间复杂度是n，但是使用递归来计算，时间复杂度是n的n次方。
        */
        int[] ints = new int[45];
        ints[0]=1;
        ints[1]=2;
        for (int i = 2; i <ints.length; i++) {
            ints[i]=ints[i-1]+ints[i-2];
            System.out.println(ints[i]);
        }



    }

}
